package q1049_lastStoneWeightII;

public class Solution {
    /**
     * 为什么此题也是利用背包问题的解法？
     * 这里的理解就是 将石头尽量分成两堆重量相近的堆 然后进行粉碎
     * 比如 2,7,4,1,8,1 我们期望能够分成 2，7，1，1 和 4，8
     * 所以又重新演变成为了01背包问题 也就是416题，如果我们使用总重量sum一半的背包 我们最多能够装多少石头？
     * 那么就又可以使用模板解决
     */
    public int lastStoneWeightII(int[] stones) {
        // 先求出石头的总重量
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }

        int maxNum = sum / 2;

        int[] dp = new int[maxNum + 1];
        for(int i = 0; i < stones.length; i++) { // 遍历所有我们能用的石头
            for(int j = maxNum; j >= stones[i]; j--) { // 遍历我们dp的容量 注意要倒序遍历 并且条件要是j >= nums[i]
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        // maxNum向下取整，所以 sum - dp[maxNum] 一定比 dp[maxNum] 大
        return (sum - dp[maxNum]) - dp[maxNum];

    }
}
